package problem94_Binary_Tree_Inorder_Traversal;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import problem94_Binary_Tree_Inorder_Traversal.MySolution.TreeNode;

public class MySolutionNonRecursive {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result=new LinkedList<>();
		Stack<TreeNode> stack=new Stack<>();
		while(true){
			while(root!=null){
				stack.push(root);
				root=root.left;
			}
			if(!stack.isEmpty()){
				TreeNode curr=stack.pop();
				result.add(curr.val);
				root=curr.right;
			}else{
				break;
			}
		}
		return result;
	}
}
